#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int reversePairs(vector<int>& record) {
        if (record.empty()) return 0;
        vector<int>temp(record.size());
        return sorthelper(record, temp, 0, record.size() - 1);
    }
private:
    int sorthelper(vector<int>& record, vector<int>& temp, int left, int right) {
        if (left >= right)return 0;
        int mid = left + (right - left) / 2;
        int count = sorthelper(record, temp, left, mid) + sorthelper(record, temp, mid + 1, right);
        count += merge(record, temp, left, mid, right);
        return count;
    }
    int merge(vector<int>& nums, vector<int>& temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;
        int count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            }
            else {
                temp[k++] = nums[j++];
                count += (mid - i + 1);
            }
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];

        for (int p = left; p <= right; p++) {
            nums[p] = temp[p];
        }

        return count;
    }
};